﻿/*
 * @autor: hectorea
 * @date: 25/07/12
 * @project: RGBSorted
 */

using System;
using System.Diagnostics;

namespace RGBSorted
{
    /// <summary>
    /// There is an array consisting of Values R, G, B in a random order. 
    /// We have to move all R’s left side and all B’s right side and we have to place 
    /// all G’s in the middle
    /// <example>
    /// INPUT: string[] a = { "R", "G", "B", "R", "G", "B","R","R","B","G","B","G" }; 
    /// OUTPUT:  R  R  R  R  G  G  G  G  B  B  B  B
    /// </example>
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            string[] input = { "R", "G", "B", "R", "G", "B", "R", "R", "B", "G", "B", "G" };
            //string[] input = { "R", "G", "B", "R", "G", "B", "R", "R", "B", "G", "B", "G", "R", "G", "B", "R", "G", "B", "R", "R", "B", "G", "B", "G" };

            sw.Start();
            string[] result = SortRGBHardCode(input);
            //string[] result = SortRGB(input, new string[] {"R","G","B"});
            sw.Stop();

            Console.WriteLine("Elpased Time: {0} ms", sw.ElapsedMilliseconds);
            Console.WriteLine("Elpased Time: {0} ticks", sw.ElapsedTicks);

            for (int i = 0; i < result.Length; i++)
                Console.Write(" {0} ", result[i]);

            Console.ReadLine();
        }

        #region [ Split Approach]
        /// <summary>
        /// Split the input array in left, center and rigth arrays and then merge them in one array previously ordered
        /// </summary>
        /// <param name="input">Input array containing the string values</param>
        /// <param name="order">Set the order we want sort the input array</param>
        /// <returns>An array orderded based on the order criteria passed as parameter</returns>
        public static string[] SortRGB(string[] input, string[] order)
        {
            if (input.Length <= 0)
                throw new ArgumentNullException("The input array cannot be null or empty");

            if (order.Length <= 0)
                throw new ArgumentNullException("The array of the values order cannot be null or empty");

            string[] left = new string[0];
            string[] center = new string[0];
            string[] rigth = new string[0];


            for (int i = 0; i < input.Length; i++)
            {
                if (input[i].Equals(order[0]))              //left values
                {
                    left = Resize(left, input[i]);
                }
                else if (input[i].Equals(order[1]))         //center values
                {
                    center = Resize(center, input[i]);
                }
                else if (input[i].Equals(order[2]))         //rigth values
                {
                    rigth = Resize(rigth, input[i]);
                }
            }

            return Merge(left, center, rigth);
        }
        /// <summary>
        /// Resize the input array in one
        /// </summary>
        /// <param name="input">The current array </param>
        /// <param name="value">The value that we want to add to the current array</param>
        /// <returns>The input array resized with the value passed as parameter</returns>
        private static string[] Resize(string[] input, string value)
        {
            string[] temp = new string[input.Length + 1];

            for (int i = 0; i < temp.Length - 1; i++)
                temp[i] = input[i];

            temp[temp.Length - 1] = value;

            return temp;
        }
        /// <summary>
        /// Merge the arrays in one array
        /// </summary>
        /// <param name="left">Array cointaining the left values</param>
        /// <param name="center">Array cointaining the center values</param>
        /// <param name="rigth">Array cointaining the rigth values</param>
        /// <returns>One array with the values sorted in the order desired</returns>
        private static string[] Merge(string[] left, string[] center, string[] rigth)
        {
            int count = 0;
            string[] temp = new string[left.Length + center.Length + rigth.Length];

            for (int i = 0; i < left.Length; i++)
                temp[count++] = left[i];
            for (int i = 0; i < center.Length; i++)
                temp[count++] = center[i];
            for (int i = 0; i < rigth.Length; i++)
                temp[count++] = rigth[i];

            return temp;
        }
        #endregion

        #region [ Hardcoded ]
        protected const string R = "R";
        protected const string G = "G";
        protected const string B = "B";

        /// <summary>
        /// This approach assumes that always we'll receive an array with R, G, B values in a random order
        /// </summary>
        /// <param name="input">Input array with R, G, B values in a random order </param>
        /// <returns>An array with the Rs at the left, the Gs in the middle and the Bs at the rigth</returns>
        public static string[] SortRGBHardCode(string[] input)
        {
            int count = 0;
            string[] temp = new string[input.Length];

            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == R)
                    temp[count++] = input[i];
            }
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == G)
                    temp[count++] = input[i];
            }
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == B)
                    temp[count++] = input[i];
            }

            return temp;
        }
        #endregion
    }    
}
